package binaryTree;

import java.util.HashMap;
import java.util.Map;

/*
 *@description 实现 Trie (前缀树)
 *@author hkfan
 *@version 1.0
 *@create 2025/6/24 09:23
 */
public class LeetCode_208 {
    class Trie {

        class Node{
            char val;
            int cross;
            int end;
            Map<Character,Node> map;

            public Node(char val, int cross, int end) {
                this.val = val;
                this.cross = cross;
                this.end = end;
                this.map = new HashMap<>();
            }
        }

        Node root;

        public Trie() {
            root = new Node('0',0,0);
        }

        public void insert(String word) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                if (cur.map.containsKey(word.charAt(i))){
                    cur.cross++;
                }else {
                    Node node = new Node(word.charAt(i), 1, 0);
                    cur.map.put(word.charAt(i),node);
                }
                cur = cur.map.get(word.charAt(i));
            }
            cur.end++;
        }

        public boolean search(String word) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                if (!cur.map.containsKey(word.charAt(i))){
                    return false;
                }
                cur = cur.map.get(word.charAt(i));
            }
            if (cur.end!=0){
                return true;
            }
            return false;
        }

        public boolean startsWith(String prefix) {
            Node cur = root;
            for (int i = 0; i < prefix.length(); i++) {
                if (!cur.map.containsKey(prefix.charAt(i))){
                    return false;
                }
                cur = cur.map.get(prefix.charAt(i));
            }
            if (cur.cross!=0){
                return true;
            }
            return false;
        }
    }
}
